package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

public class EditDistance {

    /**
     * 动态规划
     * dp[i][j] = {
     *     word1[i] == word2[j], dp[i - 1][j - 1]
     *     word1[i] != word2[j], min(dp[i][j + 1],dp[i + 1][j],dp[i + 1][j + 1]) + 1
     * }
     */
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        if (len1 == 0 || len2 == 0){
            return len1 + len2;
        }
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; ++i){
            // 初始删除的值
            dp[i][0] = i;
        }
        for (int i = 1; i <= len2; ++i){
            // 初始插入的值
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; ++i){
            for (int j = 1; j <= len2; ++j){
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                if (c1 == c2){
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }


    public static void main(String[] args) {
//        String w1 = "horse";
//        String w2 = "ros";
        String w1 = "a";
        String w2 = "ab";
        int i = new EditDistance().minDistance(w1, w2);
        System.out.println(i);
    }

}
